package cyc2018.二分查找.原理;

/**
 * 寻找比目标字母大的最小字母
 */
public class Test744 {

    public static char nextGreatestLetter(char[] letters, char target) {
        int n = letters.length;
        int start = 0;
        int end = n - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            // 此处需要使用 <= 号，如此一来，最终 start 就是要返回的对象
            if (letters[mid] <= target) {
                start = mid + 1;
            }  else {
                end = mid - 1;
            }
        }
        // 找到最后了还是没找到，则需要返回第一个元素
        // 不然返回 start 指向的元素
        return start < n ? letters[start] : letters[0];
    }

    public static void main(String[] args) {
        char[] letters = {'c', 'f', 'j', 'k', 'o', 'q'};
        char target = 'n';
        System.out.println(nextGreatestLetter(letters, target));
    }
}
